class Solution {
    /*
        思路1：栈
        遍历过程提前返回false：对于每个右括号，如果不能消去，那么表达式一定是非法的，
        即栈不能包含右括号
    */
    public boolean isValid(String s) {
        Deque<Character> q = new LinkedList<>();
        for (int i = 0, len = s.length(); i < len; i++) {
            char ch = s.charAt(i);
            if (q.size() > 0) {
                char tot = q.peekLast(); // 取出队尾元素，可能为null
                if (tot == '(' && ch == ')' ||
                        tot == '[' && ch == ']' ||
                        tot == '{' && ch == '}'
                ) {
                    q.pollLast();
                } else {
                    q.offerLast(ch);
                }
            } else {
                q.offerLast(ch);
            }
        }
        return q.size() == 0;
    }
}